package ShuJuJieGou;

import java.util.Scanner;

public class LinkedListSorting {
    // 构建链表
    public static ListNode buildLinkedList(int[] data) {
        if (data.length == 0) {
            return null;
        }
        ListNode head = new ListNode(data[0]);
        ListNode current = head;
        for (int i = 1; i < data.length; i++) {
            current.next = new ListNode(data[i]);
            current = current.next;
        }
        return head;
    }

    // 升序排序链表（冒泡排序思想）
    public static ListNode sortLinkedListAscending(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        boolean swapped;
        ListNode end = null;
        do {
            swapped = false;
            ListNode current = head;
            while (current.next != end) {
                if (current.val > current.next.val) {
                    int temp = current.val;
                    current.val = current.next.val;
                    current.next.val = temp;
                    swapped = true;
                }
                current = current.next;
            }
            end = current;
        } while (swapped);
        return head;
    }

    // 打印链表
    public static void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void basicVersion() {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入你的学号（去掉P后的数字）：");
        int studentId = sc.nextInt();
        int[] baseData = {111, 333, 9999, 66, 112, 213, 447, 168, 1, 4321, 8787, studentId};
        ListNode head = buildLinkedList(baseData);
        head = sortLinkedListAscending(head);
        printLinkedList(head);
    }
}
